/**
 * 01背包应用----背包是否正好装满
 * 给你一个 只包含正整数 的 非空 数组 nums 。
 * 请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]

拆分： 元素和相等 存在tagrget=sum/2 判断奇数情况
nums的元素是否可一拼凑出和为target
【从集合中取元素，的到正好等于target的子集】
类比01背包， 价值和重量都是子集元素本身

dp[j] 目标值j的所有元素的最大和 
 */
var canPartition = function (nums) {
  let sum = nums.reduce((a, b) => a + b);
  if (sum & 1) return false; //sum&1 按位与运算-判断奇数/偶数：奇数二进制最后一位为1 偶数是0

  const target = sum / 2;
  const dp = Array(target + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
    }
  }
  return dp[target] == target;
};
/**
 * review1210✅
 */
const nums = [1,5,11,5];
console.log('分割等和子集', canPartition(nums));  //true